#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

// 30. 串联所有单词的子串
// https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

class Solution
{
public:
    vector<int> findSubstring(string s, vector<string> &words)
    {
        unordered_map<string, int> recordWordCount;

        for (auto it : words)
        {
            ++recordWordCount[it];
        }
        int wordLen = words[0].size();
        int windowLen = words.size() * wordLen;

        vector<int> ans;

        for (int begin = 0; begin < wordLen; begin++)
        {
            unordered_map<string, int> recordSubStrCount;
            int overload = 0;
            int left = begin;
            for (int right = left; right < s.size(); right += wordLen)
            {
                string curWord = s.substr(right, wordLen);

                // 剪枝
                if(recordWordCount.find(curWord) == recordWordCount.end()){
                    left = right + wordLen;
                    recordSubStrCount.clear();
                    overload = 0;
                    continue;
                }

                if(recordSubStrCount[curWord] >= recordWordCount[curWord]){
                    ++overload;
                }
                ++recordSubStrCount[curWord];

                // 窗口的建立
                if(right - left + wordLen < windowLen){
                    continue;
                }

                if(overload == 0){
                    ans.push_back(left);
                }

                string preWord = s.substr(left, wordLen);
                --recordSubStrCount[preWord];
                if(recordWordCount[preWord] <= recordSubStrCount[preWord]){
                    overload--;
                }
                // 更新窗口
                left += wordLen;
            }
        }
        return ans;
    }
};

int main()
{
    string str = "wordgoodgoodgoodbestword";
    vector<string> word{"word","good","best","word"};
    Solution solution{};
    solution.findSubstring(str, word);
    return 0;
}